#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <sys/time.h>
#define	NDEBUG
#include <assert.h>

#define RANDOM(min, max)	(rand() % ((max) - (min) + 1) + (min))

#define	INDEX_SRC_FNAME					1
#define	INDEX_DST_FNAME					2	


void print_grid_data(const char *data, int h, int w)
{
	int i, j;
	const char *p = data;

	for (i = 0; i < h; i++) {
		for (j = 0; j < w; j++) {
			printf("%d ", *(p++)); 
		}
		printf("\n");
	}
}

char *read_grid_data(const char *f_name, int *height, int *width, int *iteration)
{
	FILE *fp;
	int i, j, value;
	int row, column;
	char *data_buf, *p;
	char *row_buf;
	int row_buf_size;

	fp = fopen(f_name, "r");
	if (fp == NULL) {
		printf("Couldn't find %s, then use default file\n", f_name);
		return NULL;
	}	
	// the first two numbers
	fscanf(fp, "%d", height);
	fscanf(fp, "%d", width);
	// the third number is the number of generations
	fscanf(fp, "%d", iteration);
	
	// allocate memory after getting the height and width
	data_buf = (char *)malloc(sizeof(char) * (*height) * (*width));	
	row_buf_size = sizeof(char) * (*width) * 3;
	row_buf = (char *)malloc(row_buf_size);

	// read grid data from file to data_buf
	p = data_buf;
	while (fgets(row_buf, row_buf_size, fp) != NULL) {
		i = 0;
		while (row_buf[i] != '\0') {
			if ((row_buf[i] == '0') || (row_buf[i] == '1')) {				
				*(p++) = row_buf[i] - '0';
			}
			i++;
		}
	}
	fclose(fp);
	free(row_buf);

	return data_buf;
}

// save grid data to file
void save_grid_data(const char *f_name, const char *data, int h, int w)
{
	FILE *fp;
	int i, j, row, column, proc_h, proc_w;
	const char *p;
	char *txt_buf;
	int txt_cnt;

	txt_buf = (char *) malloc(sizeof(char) * h * (w * 2 + 1));
	fp = fopen(f_name, "w");

	p = data;
	txt_cnt = 0;
	for (i = 0; i < h; i++) {
		for (j = 0; j < w; j++) {
			*(txt_buf + txt_cnt) = *(p++) + '0';
			txt_cnt++;
			*(txt_buf + txt_cnt) = ' ';
			txt_cnt++;
		}
		*(txt_buf + txt_cnt) = '\n';
		txt_cnt++;
	}
	fwrite(txt_buf, sizeof(char), txt_cnt, fp);
	fclose(fp);
	free(txt_buf);
}

// return the cell value for next generation
int get_next_val(int val_now, int occupied_cnt)
{
	int val_next;
	if(val_now == 1) { // the cell is occupied
		if ((occupied_cnt < 2) || (occupied_cnt > 3))
			val_next = 0;
		else
			val_next = 1;
							
	} else { // the cell is empty
		if (occupied_cnt == 3)
			val_next = 1;
		else
			val_next = 0;
	}
	return val_next;
}


// update the grid data 
int update_grid_data(char *data, char *count, int len)
{
	int i, j;
	for (i = 0; i < len; i++) {
		data[i] = get_next_val(data[i], count[i]);
	}
	return 0;
}

// flag = 0, don't check the elements at the edge
// count the neighbors one time
int cacl_conway_cnt_once(char *count, char *data, int height, int width, int flag)
{
	int i, j, m, n;
	int occupied_cnt = 0;
	int n_occup_cnt, s_occup_cnt, w_occup_cnt, e_occup_cnt;
	char **ptr_data, **ptr_count;

	//data_buf = (char **)malloc(sizeof(char *) * height);
	ptr_data = (char **)malloc(sizeof(char *) * height);
	ptr_count = (char **)malloc(sizeof(char *) * height);
	
	assert(count != data);
	// initialize the pointer
	for (i = 0; i < height; i++) {
		ptr_data[i] = data + i * width;
		ptr_count[i] = count + i * width;
	}

	// caculate the grid data except the cells at the edge
	for (i = 1; i < height - 1; i++) {
		for (j = 1; j < width -1; j++) {

			//caculate the number of occupied elements in the neighbors	
			occupied_cnt = 0;
			occupied_cnt += ptr_data[i - 1][j - 1] + ptr_data[i - 1][j] + ptr_data[i - 1][j + 1];
			occupied_cnt += ptr_data[i][j - 1] + ptr_data[i][j + 1];
			occupied_cnt += ptr_data[i + 1][j - 1] + ptr_data[i + 1][j] + ptr_data[i + 1][j + 1];
			assert((occupied_cnt <= 8) && (occupied_cnt >= 0));

			// save the count	
			ptr_count[i][j] = occupied_cnt;
				
		}
	}

	if ( flag == 1) { // caculate the elements at edge
		// caculate north and south edge
		for (i = 1; i < width - 1; i++) {
			n_occup_cnt = 0;
			s_occup_cnt = 0;
			for (m = 0; m < 2; m++) {
				for (n = i- 1; n <= i + 1; n++) {
					n_occup_cnt += ptr_data[m][n];
					s_occup_cnt += ptr_data[height - 1 - m][n];
				}
			}
			n_occup_cnt -= ptr_data[0][i];
			s_occup_cnt -= ptr_data[height - 1][i];
			ptr_count[0][i] = n_occup_cnt;
			ptr_count[height - 1][i] = s_occup_cnt;
		} 

		// caculate west and east edge
		for (i = 1; i < height - 1; i++) {
			w_occup_cnt = 0;
			e_occup_cnt = 0;
			for (m = i - 1; m <= i + 1; m++) {
				for (n = 0; n < 2; n++) {
					w_occup_cnt += ptr_data[m][n];
					e_occup_cnt += ptr_data[m][width - 1 - n];
				}
			}
			w_occup_cnt -= ptr_data[i][0];
			e_occup_cnt -= ptr_data[i][width - 1];
			ptr_count[i][0] = w_occup_cnt;
			ptr_count[i][width - 1] = e_occup_cnt;
		} 

		// four vetexes
		occupied_cnt = ptr_data[0][1] + ptr_data[1][0] + ptr_data[1][1];
		ptr_count[0][0] = occupied_cnt;

		occupied_cnt = ptr_data[0][width - 2] + ptr_data[1][width - 1] + ptr_data[1][width - 2];
		ptr_count[0][width - 1] = occupied_cnt;

		occupied_cnt = ptr_data[height - 2][0] + ptr_data[height - 1][1] + ptr_data[height - 2][1];
		ptr_count[height - 1][0] = occupied_cnt;

		occupied_cnt = ptr_data[height - 1][width - 2] + ptr_data[height - 2][width - 1] + ptr_data[height - 2][width - 2];
		ptr_count[height - 1][width - 1] = occupied_cnt;

	} 

	free(ptr_data);
	free(ptr_count);
	return 0;
}


int serial_conway(char *data, int height, int width, int iteration)
{
	int i;
	char *grid_cnt;

	grid_cnt = (char *) malloc(sizeof(char) * height * width);

	for (i = 0; i < iteration; i++) {
		cacl_conway_cnt_once(grid_cnt, data, height, width, 1);
		update_grid_data(data, grid_cnt, height * width);
	}

	free(grid_cnt);
	return 0;
}


int main(int argc, char *argv[])
{
	int i;	
	int w, h, iteration;	// widht, height
	char *grid_data;

	//time_t t_start, t_end;	
	//time_t t_ser_start, t_ser_end;	
	struct timeval t_start, t_end;	
	struct timeval t_ser_start, t_ser_end;	
	
	if (argc < 3) { 
		// if you don't specify the name of the source and destination file
		printf("Error: too few arguments.\n");
		return 1;
	} else { //read the file you specified

		//t_start = time(NULL);
		gettimeofday(&t_start, NULL);
		printf("reading data from file...\n");
		grid_data = read_grid_data(argv[INDEX_SRC_FNAME], &h, &w, &iteration);
		if (grid_data == NULL)
			return 1;
		printf("h: %d w: %d iter : %d\n", h, w, iteration);
	}

	gettimeofday(&t_ser_start, NULL);
	//t_ser_start = time(NULL);
	serial_conway(grid_data, h, w, iteration);
	//t_ser_end = time(NULL);
	gettimeofday(&t_ser_end, NULL);

	printf("saving data to file...\n");
	save_grid_data(argv[INDEX_DST_FNAME], grid_data, h, w);		
	gettimeofday(&t_end, NULL);
	//t_end = time(NULL);
	
	free(grid_data);
	printf("###total run-time: %f s\n", (t_end.tv_sec - t_start.tv_sec) + (t_end.tv_usec - t_start.tv_usec) * 0.000001);
	printf("###serial-alg rum-time: %f s\n", (t_ser_end.tv_sec - t_ser_start.tv_sec) + (t_ser_end.tv_usec - t_ser_start.tv_usec) * 0.000001);
	//printf("###serial-alg rum-time: %f s\n", difftime(t_ser_end, t_ser_start));
	
	return 0;
}
